package top100.backtrack;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author ZhangCuirong
 * @Date 2025/7/16 12:34
 * @description:
 * 给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "aab"
 * 输出：[["a","a","b"],["aa","b"]]
 * 示例 2：
 *
 * 输入：s = "a"
 * 输出：[["a"]]
 *
 *
 * 提示：
 *
 * 1 <= s.length <= 16
 * s 仅由小写英文字母组成
 */
public class Solution131 {
    public boolean isPalindrome(String s, int start, int end){
        while(start < end){
            if(s.charAt(start) != s.charAt(end)){
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
    public void backtrack(String s, int start, LinkedList<String> path, List<List<String>> res) {
        if(start == s.length()){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = start; i < s.length(); i++){
            if(isPalindrome(s, start, i)){
                path.addLast(s.substring(start, i + 1));
                backtrack(s, i + 1, path, res);
                path.removeLast();
            }
        }
    }
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        backtrack(s, 0, new LinkedList<>(), res);
        return res;
    }

    public static void main(String[] args) {
        Solution131 s = new Solution131();
        String s1 = "aab";
        List<List<String>> res = s.partition(s1);
        System.out.println(res);


    }

}
